package com.example.demo.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * 实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
 *
 *     BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
 *     boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
 *     int next()将指针向右移动，然后返回指针处的数字。
 *
 * 注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
 *
 * 可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。
 *
 *
 *
 * 示例：
 *
 * 输入
 * inputs = ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
 * inputs = [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
 * 输出
 * [null, 3, 7, true, 9, true, 15, true, 20, false]
 *
 * 解释
 * BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
 * bSTIterator.next();    // 返回 3
 * bSTIterator.next();    // 返回 7
 * bSTIterator.hasNext(); // 返回 True
 * bSTIterator.next();    // 返回 9
 * bSTIterator.hasNext(); // 返回 True
 * bSTIterator.next();    // 返回 15
 * bSTIterator.hasNext(); // 返回 True
 * bSTIterator.next();    // 返回 20
 * bSTIterator.hasNext(); // 返回 False
 *
 *
 *
 * 提示：
 *
 *     树中节点的数目在范围 [1, 105] 内
 *     0 <= Node.val <= 106
 *     最多调用 105 次 hasNext 和 next 操作
 *
 *
 *
 */
//
public class LEECODE {
//    String[] inputs = {"BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"};
//    int  in= 0;
//    public  Integer dfs( Integer[] arr,int target ,int index){
//        if(arr[target] == null && arr[target+1] == null){
//            return null;
//        }
//            Integer l = dfs(arr, target+2*index,index+1);
//
//            dfs(arr, target+2*index+1,index+1);
//            return 0;
//    }
//    static  int a[];
//    static  int c=0;
//    static  boolean bs[];
//    public static void main(String[] args) {
////        String s = "asda";
////        a=new int[s.length()];
////        bs=new boolean[s.length()];
////        dfs(1,1,s,a,0);
////        System.out.println(Arrays.toString(a));
//        process(new String[]{"R","L",".","R"});
//    }
//    public static void dfs(int b,int times,String s,int a[],int index){
//        if(index >= a.length){
//            return;
//        }
//        if(times==0){
//            a[b-1]++;
//            times = b+1;
//            b = times;
//        }
//        Set<String> set=new HashSet<>();
//        for(int i =0 ;i<s.length();i++){
//            if(!set.contains(s.charAt(i)+"") && !bs[i]) {
//                bs[i]=true;
//                dfs(b, times - 1, s, a, i + 1);
//                bs[i]=false;
//            }
//            set.add(s.charAt(i)+"");
//        }
//    }
//
//
//    public static void process(String[] arr){
//        Stack<Integer> stack = new Stack<>();
//        String target[] = new String[arr.length];
//        for(int i =0;i<arr.length;i++){
//            String s = arr[i];
//            int right = i;
//            if(s.equals("L")){
//                if(stack.size()>0&&arr[stack.peek()].equals("R")){
//                    int left = 0;
//                    while (stack.size()>0&&arr[stack.peek()].equals("R")){
//                        left = stack.pop();
//                    }
//                    while (left < right){
//                        target[left] = "R";
//                        target[right] = "L";
//                        left++;
//                        right--;
//                    }
//                    if(left == right){
//                        target[left] = ".";
//                    }
//                }else {
//                    stack.add(i);
//                }
//            }else if(s.equals("R")){
//                stack.add(i);
//            }
//
//        }
//
//        while (stack.size()>0){
//            Integer pop = stack.pop();
//            if(arr[pop].equals("R")){
//                Arrays.fill(target,pop,target.length-1,"R");
//            }else{
//                Arrays.fill(target,0,pop,"L");
//            }
//        }
//        System.out.println(Arrays.toString(target));
//    }



    public static void main(String[] args) {
        String[] str= {"John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"};
        String[] relation= {"(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"};
        Map<String,String> map=new HashMap<>();
        for(String s : relation){
            String[] split = s.split(",");
//            map.put(split[0].substring(1),split[1].substring(0,split[1].length()-1));
            map.put(split[1].substring(0,split[1].length()-1),split[0].substring(1));
        }
        Map<String,Integer> count=new HashMap<>();
        for(String s : str){
            count.put(s.substring(0,s.indexOf("(")),Integer.valueOf(s.substring(s.indexOf("(")+1,s.indexOf(")"))));
        }
        Map<String,Integer> count1=new HashMap<>();
        for(String s : str){
            Integer a = count.get(s.substring(0, s.indexOf("(")));
            String s1 = find(map, s.substring(0, s.indexOf("(")));
            count1.put(s1,a+count1.getOrDefault(s1,0));
        }
        for(Map.Entry<String,Integer> m : count1.entrySet()){
            if(m.getValue() != 0){
                System.out.println(m.getKey()+"("+m.getValue()+")");
            }
        }
    }
    public static String  find(Map<String,String> map,String str){
        if(map.get(str)!=null){
            return find(map,map.get(str));
        }
        return str;
    }

    public static void process(){

    }
}
/**
 * 每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，
 * 例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。
 * 给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。
 * 设计一个算法打印出每个真实名字的实际频率。
 * 注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。
 *
 * 在结果列表中，选择 字典序最小 的名字作为真实名字。
 *
 *  
 *
 * 示例：
 *
 * 输入：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
 * 输出：["John(27)","Chris(36)"]
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/baby-names-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */


















